package mcMST;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import nsga.Individual;

import common.GeneticOperations;

public class MSTGeneticOperations implements GeneticOperations<MSTGenotype> {
	private Random rand;
	private Graph graph;
	//private double param_p;

	/**
	 * 
	 * @param aTownsMap
	 * @param p paramter dla operatora inver-over
	 */
	public MSTGeneticOperations(Graph aGraph) {
		this.graph = aGraph;
		//this.param_p = aParam_p;
	}

	@Override
	public List<Individual<MSTGenotype>> createAllResults() {
		return null;
	}

	@Override
	public MSTGenotype createGenotypeFromString(String genotype) {
		return null;
	}

	@Override
	public MSTGenotype createRandomGenotype() {

		MSTGenotype result = new MSTGenotype(this.graph.getNumOfNodes());
		return result;
	}

	/**
	 * Crossover operator
	 */
	@Override
	public List<MSTGenotype> crossover(MSTGenotype g1, MSTGenotype g2) {
		rand = new Random();
		List<Integer> pn1 = g1.getPrueferNumber();
		List<Integer> pn2 = g2.getPrueferNumber();
		int genLen = pn1.size();
		List<MSTGenotype> resultList = new ArrayList<MSTGenotype>(2);
		List<Integer> pnchild1 = new ArrayList<Integer>(genLen);
		List<Integer> pnchild2 = new ArrayList<Integer>(genLen);

		// utworzenie maski
		for(int i = 0; i < genLen; i++) {
			Double tmp = rand.nextDouble();
			if(tmp < 0.5) {
				pnchild1.add(pn1.get(i));
				pnchild2.add(pn2.get(i));
			} else {
				pnchild1.add(pn2.get(i));
				pnchild2.add(pn1.get(i));
			}
		}

		MSTGenotype gchild1 = new MSTGenotype(pnchild1);
		MSTGenotype gchild2 = new MSTGenotype(pnchild2);
		resultList.add(gchild1);
		resultList.add(gchild2);

		return resultList;
	}

	/**
	 * Mutation operator
	 * Take a random position i genotype
	 * and replace it with random index
	 */
	@Override
	public void mutate(MSTGenotype genotype) {
		List<Integer> pn = genotype.getPrueferNumber();

		int pos = rand.nextInt(pn.size());
		int elem = rand.nextInt(pn.size());
		while(pos == elem) {
			elem = rand.nextInt(pn.size());
		}

		pn.set(pos, elem);
		genotype.setPrueferNumber(pn);
	}



	@Override
	public List<Double> getFitnessesFromValue(List<Double> values) {
		return values;
	}

	@Override
	public List<Double> getValues(MSTGenotype genotype) {

		double[] result = new double[graph.getNumOfObjectives()];
		List<Integer> pn = genotype.getPrueferNumber();
		int genSize = graph.getNumOfNodes();
		List<Integer> pn2 = new ArrayList<Integer>(genSize - 2);

		for(int i = 0; i < (genSize - 2); i++) {
			pn2.add(pn.get(i));
		}


		//System.out.println("genSize " + genSize + " pn2.size() " + pn2.size());
		Integer [][] matrix = new Integer [genSize][genSize]; //macierz adiacencji drzewa
		List<Integer> leaves = new ArrayList<Integer>();

		// Wyzerowanie macierzy adiacencji
		for(int i = 0; i < genSize; i++) {
			for(int j = 0; j < genSize; j++) {
				matrix[i][j] = 0;
			}
		}

		// get leaves
		for(int i = 0; i < genSize; i++) {
			leaves.add(i);
		}
		for(int i = 0; i < genSize - 2; i++) {
			leaves.remove(pn2.get(i));
		}
		// Debug
		/*System.out.println("liscie: " + leaves.size());
		for(int i = 0; i < leaves.size(); i++) {
			System.out.print(leaves.get(i) + " ");
		}*/

		// decode pruefer number to a tree
		while(pn2.size() > 0) {
			matrix[leaves.get(0)][pn2.get(0)]++;
			matrix[pn2.get(0)][leaves.get(0)]++;
			leaves.remove(0);
			Integer elem = pn2.remove(0);
			//System.out.println("elem " + elem);
			if(!(pn2.contains(elem))) {
				//System.out.println("Rozmiar lisci przed " + leaves.size());
				leaves.add(elem);
				//System.out.println("Rozmiar lisci po" + leaves.size());
				Collections.sort(leaves, new Comparator<Integer>() {
					@Override
					public int compare(Integer o1, Integer o2) {
						if(o1 < o2)
							return -1;
						else if(o1 > o2)
							return 1;
						else
							return 0;
					}
				});
			}
		}
		//System.out.println("pozostaly rozmiar lisci: " + leaves.size());
		matrix[leaves.get(0)][leaves.get(1)]++;
		matrix[leaves.get(1)][leaves.get(0)]++;



		//Debug
		/*System.out.println();
		for(int i = 0; i < genSize; i++) {
			for(int j = 0; j < genSize; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}*/

		// get sum
		for(int i = 0; i < genSize; i++) {
			for(int j = 0; j < genSize; j++) {
				if(matrix[i][j] == 1) {
					for (int objNum = 0; objNum < graph.getNumOfObjectives(); objNum++) {
						result[objNum] += graph.getEdgeWeight(i, j, objNum);
						matrix[i][j]--;
						matrix[j][i]--;
						//System.out.println("wartosc w grafie: " + graph.getEdgeWeight(i, j, objNum));
					}
				}
			}
		}

		List<Double> resultList = new ArrayList<Double>(graph.getNumOfObjectives());
		for (double r : result) {
			resultList.add(r);
		}
		return resultList;
	}


	@Override
	public MSTGenotype duplicateGenotype(MSTGenotype genotype) {
		return new MSTGenotype(genotype);
	}

}

